package com.ly.algorithm.offerpointer;


/**
 * @Classname Offer14_I
 * @Description
 *
 * 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
 *
 * 示例 1：
 *
 * 输入: 2
 * 输出: 1
 * 解释: 2 = 1 + 1, 1 × 1 = 1
 * 示例 2:
 *
 * 输入: 10
 * 输出: 36
 * 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
 *
 *
 * @Date 2021/1/26 16:09
 * @Author 冷心影翼
 */
public class Offer14I {

    public static void main(String[] args) {
        Solution14I solution14I = new Solution14I();
        System.out.println(solution14I.cuttingRopeByDP(10));
        System.out.println(solution14I.cuttingRopeByRecursion(10));
        System.out.println(solution14I.cuttingRopeByMath(10));
    }
}



class Solution14I {
    public int cuttingRopeByDP(int n) {
        int[] dp = new int[n+1];
        dp[2] = 1;
        for (int i = 3; i <=n ; i++) {
            for (int j = 2; j < i; j++) {
                dp[i] = Math.max(dp[i],Math.max(j*(i-j),dp[i-j]*j));
            }
        }
        return dp[n];
    }

    private int[] memory;

    public int cuttingRopeByRecursion(int n) {
        memory = new int[n+1];
        memory[2] = 1;
        return cuttingRopeByRecursion2(n);
    }

    public int cuttingRopeByRecursion2(int n) {
        if(memory[n] != 0) {
            return memory[n];
        }
        int res = 0;
        for (int i = 2; i < n; i++) {
            res = Math.max(res,Math.max(i*(n-i),i*cuttingRopeByRecursion2(n-i)));
        }
        memory[n] = res;
        return memory[n];
    }

    public int cuttingRopeByMath(int n) {
        if(n<=3) {
            return n-1;
        }
        int res = 1;
        while (n>4) {
            res = res*3;
            n-=3;
        }
        return res*n;
    }

}
